As single chemotherapeutic agents, cisplatin and paclitaxel have each been shown to have clinical utility in transitional-cell cancer of the urothelium. This phase-II study will therefore examine the two agents in combination in these subjects. The primary objective is to evaluate the combination of cisplatin and paclitaxel with respect to antineoplastic activity, as measured by the overall response rate. Overall survival and toxicity will also be assessed. A two-stage sampling design will be used, with a maximum accrual of 51 patients. Paclitaxel will be administered intravenously at a dose of 175 mg/m2 over 3 hours on day 1 of each 21-day cycle. Cisplatin will be administered by a free-flowing intravenous line at a dose of 75 mg/m2 over 30-120 minutes on day 1 of each 21-day cycle. Also, since p53 accumulation in the nuclei of transitional-cell carcinoma cells has been shown to be a statistically significant predictor of disease recurrence and death independent of tumor grade, stage and lymph-node status, the investigators will examine p53 levels in tumor paraffin blocks.